package leetcode_500;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;

public class FrogJump_403 {
	List<Integer> stone;
	int[] stones;
	public static void main(String[] args) {
		FrogJump_403 test=new FrogJump_403();
		System.out.println(test.canCross(new int[] {0,1,3,5,6,8,12,17}));
		System.out.println(test.canCross(new int[] {0,1,2,3,4,8,9,11}));
	}
	
	/**
	 * describe:正确做法 用hash n^2搜索 每次从当前元素存的map里搜索 AC 67%
	 * 2018年7月19日 上午9:13:10
	 */
	public boolean canCross(int[] stones) {
        int len = stones.length;
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for (int i = 0; i < len; i ++) {
            map.put(stones[i], new HashSet<>());
        }
        map.get(0).add(1);
        for (int i = 0; i < len - 1; i ++) {
            for (int step : map.get(stones[i])) {
                int to = step + stones[i];
                if (to == stones[len - 1]) {
                    return true;
                }
                HashSet<Integer> tmp = map.get(to);
                if (tmp != null) {
                    tmp.add(step);
                    if (step > 1) {
                        tmp.add(step - 1);
                    }
                    tmp.add(step + 1);
                }
            }
        }
        return false;
    }

	/**
	 * describe:回溯递归 超时
	 * 2018年7月18日 下午8:50:51
	 */
	public boolean canCross2(int[] stones) {
		if(stones[1]!=1)
			return false;
		 if(stones.length==2)
	            return true;
		this.stones=stones;
		this.stone=new ArrayList<Integer>();
		for(int i:stones)
			stone.add(i);
        return help(1,1);
    }
	
	/**
	 * describe:动态规划 思想错误 后面的会将前面的状态覆盖
	 * 2018年7月18日 下午8:30:52
	 */
	public boolean canCross1(int[] stones) {
		if(stones[1]!=1)
			return false;
        int dp1[]=new int[stones.length];
        int dp2[]=new int[stones.length];
        int dp3[]=new int[stones.length];
		dp1[1]=1;
		List<Integer> stone=new ArrayList<Integer>();
		for(int i:stones)
			stone.add(i);
		for(int i=1;i<stones.length-1;++i) {
			Integer temp=0;
			if(dp1[i]!=0) {
				if(dp1[i]!=1) {//避免原地踏步
					temp=stones[i]+dp1[i]-1;
					if(stone.contains(temp)) {
						dp1[stone.indexOf(temp)]=dp1[i]-1;
					}
				}
				temp=stones[i]+dp1[i];
				if(stone.contains(temp)) {
					dp2[stone.indexOf(temp)]=dp1[i];
				}
				temp=stones[i]+dp1[i]+1;
				if(stone.contains(temp)) {
					dp3[stone.indexOf(temp)]=dp1[i]+1;
				}
			}
			if(dp2[i]!=0) {
				temp=stones[i]+dp2[i]-1;
				if(stone.contains(temp))
					dp1[stone.indexOf(temp)]=dp2[i]-1;
				temp=stones[i]+dp2[i];
				if(stone.contains(temp))
					dp2[stone.indexOf(temp)]=dp2[i];
				temp=stones[i]+dp2[i]+1;
				if(stone.contains(temp))
					dp3[stone.indexOf(temp)]=dp2[i]+1;
			}
			if(dp3[i]!=0) {
				temp=stones[i]+dp3[i]-1;
				if(stone.contains(temp))
					dp1[stone.indexOf(temp)]=dp3[i]-1;
				temp=stones[i]+dp3[i];
				if(stone.contains(temp))
					dp2[stone.indexOf(temp)]=dp3[i];
				temp=stones[i]+dp3[i]+1;
				if(stone.contains(temp))
					dp3[stone.indexOf(temp)]=dp3[i]+1;
			}
		}
		return dp1[stones.length-1]+dp2[stones.length-1]+dp3[stones.length-1]
				==0?false:true;
    }
	
	
	/**
	 * describe:错误的根源 是contains算法 因为一直搜索会使集合大的用例超时
	 * 2018年7月19日 上午9:11:48
	 */
	public boolean help(int index,int step) {
		Integer temp=0;
		int now=0;
		temp=this.stones[index]+step+1;
		if(this.stone.contains(temp)) {
			now=stone.indexOf(temp);
			if(now==this.stones.length-1)
				return true;
			if(help(now,step+1))
				return true;
		}
		temp=this.stones[index]+step;
		if(this.stone.contains(temp)) {
			now=stone.indexOf(temp);
			if(now==this.stones.length-1)
				return true;
			if(help(now,step))
				return true;
		}
		if(step!=1) {
			temp=this.stones[index]+step-1;
			if(this.stone.contains(temp)) {
				now=stone.indexOf(temp);
				if(now==this.stones.length-1)
					return true;
				if(help(now,step-1))
					return true;
			}
		}
		return false;
	}
}
